package com.zjsru.plan2024.oneday;

/**
 * 使二叉树所有路径值相等的最小代价
 * 满二叉树的路径值
 * @Author: cookLee
 * @Date: 2024-02-28
 */
public class MinIncrements {

    /**
     * 主
     * \
     * 输入：n = 7, cost = [1,5,2,2,3,3,1]
     * 输出：6
     * 解释：我们执行以下的增加操作：
     * - 将节点 4 的值增加一次。
     * - 将节点 3 的值增加三次。
     * - 将节点 7 的值增加两次。
     * 从根到叶子的每一条路径值都为 9 。
     * 总共增加次数为 1 + 3 + 2 = 6 。
     * 这是最小的答案。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        MinIncrements minIncrements = new MinIncrements();
        int n = 7;
        int[] cost = new int[]{1,5,2,2,3,3,1};
        System.out.println(minIncrements.minIncrements(n, cost));
    }

    /**
     * 最小增量:从叶子节点出发开始计算
     *
     * @param n    n
     * @param cost 成本
     * @return int
     */
    public int minIncrements(int n, int[] cost) {
        int ans = 0;
        for (int i = n - 2; i > 0; i -= 2) {
            //相邻两个节点的差值，即是需要执行增加操作的值
            ans += Math.abs(cost[i] - cost[i + 1]);
            //满二叉树, 叶节点 i 和 i+1 的双亲节点下标为 i/2（整数除法）,同步加到父节点上，差值不变
            cost[i / 2] += Math.max(cost[i], cost[i + 1]);
        }
        return ans;
    }

}
